package practice;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @description:
 * @author: zhaoyinglin
 * @date: 2024/3/6
 */
public class Test {

    public static void main(String[] args) {

        int[] nums = new int[] { 0, -1, 1 };

        List<List<Integer>> result = permute(nums);

        System.out.println(result);
    }

    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();

        Set<Integer> visited = new HashSet<>();

        dfs(result, new ArrayList<>(), nums, visited);

        return result;
    }

    private static void dfs(List<List<Integer>> result, List<Integer> oneBatch, int[] nums, Set<Integer> visited) {

        if (oneBatch.size() == nums.length) {

            List<Integer> oneBatchCopy = new ArrayList<>(oneBatch);

            result.add(oneBatchCopy);
            return;
        }

        for (int num : nums) {
            if (visited.contains(num)) {
                continue;
            }

            visited.add(num);
            oneBatch.add(num);
            dfs(result, oneBatch, nums, visited);
            oneBatch.remove(oneBatch.size() - 1);
            visited.remove(num);
        }

    }

}
